package DataStructure.DP;

/**
 * @Author：DijaH
 * @Date：2023/1/19 5:07 下午
 * @Version：1.0.0
 * @Description：
 * 按键：A、ctrl-A、ctrl-C、ctrl+V
 * 按N次，可以在屏幕上输入最多的A
 */
public class code1_maxA {
    //使用动态规划，一维数组即可
    public static int maxA(int N){
        int [] dp = new int[N + 1];
        dp[0] = 0;
        //还有多少步
        for (int i = 0; i < N; i++){
            //当前位置输入A,步骤少了1，而且只在屏幕上多了一个A
            dp[i] = dp[i - 1] + 1;

            //当前位置 全选，复制，粘贴
            //连续粘贴 i - j
            //屏幕上一共 dp[j-2] * (i - j + 1)
            //之所以 j == 2 是因为 全选，复制是要两步
            for (int j = 2; j < i; j++){
                //比较dp[i] 和 dp[j-2] * (i - j + 1)
                dp[i] = Math.max(dp[i],dp[j-2] * (i - j + 1));
            }
        }
        return dp[N];
    }

    public static void main(String[] args) {

    }
}
